package com.zx._12_算法.剑指offer._2022;

/**
 * https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 */
public class 圆圈中最后剩下的数字 {

    /*
       思路：使用数学方法(先举例)
             n=5,m=3  你要知道最后的结果是3，带着结果去看问题

           第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
           (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
           第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
           第三次，【1, 3, 4】，本轮要踢出4                                        看1
           第四次，【1, 3】 本轮要踢出1                                            看3
           第五次，【3】
           最后返回3

           我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
           你从第二次，向上看第一次
           你会发现，原来3在0的位置
                   现在，3在(0 + 3) % 2
                           => +3 回到上次的位置
                           => %5 防止数组溢出，并且数组本来就是循环数组
                    所有推算过程：
                    4：    (0 + 3) % 2 = 1
                    3：    (1 + 3) % 3 = 1
                    2：    (1 + 3) % 4 = 0
                    1：    (0 + 3) % 5 = 3

           f(n) = ( f(n - 1) + m ) % n
           解释意思：
               f(n) 表示上一次
               f(n - 1) 表示这次，因为我们要从这次回推上一次
               m 表示隔几个
               n表示上一次的数组长度

        */
    public int lastRemaining(int n, int m) {
        int f = 0;
        // 反向推算最开始的位置
        // i 表示当前的数据量
        for (int i = 2; i < n + 1; i++) {
            f = (m + f) % i;
        }

        return f;
    }

}
